package d2;
import java.util.*;

public class Day9 {

    public static void main1(String[] args) {
        int c = 97;
        System.out.println((char)c);

        char ch = 'a';
        int num = (int)ch -97;
        System.out.println(Character.isUpperCase(ch));

        String s = "AAA";
        String ret = s.toLowerCase();

        //System.out.println(ret);
        char[] str = s.toCharArray();
    }

    public static void main(String[] args) {
        List<String> s = new ArrayList<>();
        s.add("hot");
        s.add("dot");
        s.add("dog");
        s.add("lot");
        s.add("log");
        //ladderLength("hit","cog",s);
    }
    //单词接龙
    public int minMutation(String startGene, String endGene, String[] bank) {
        if(startGene.equals(endGene)) return 0;//优化1
        Set<String> set = new HashSet<>();
        for(String s:bank) set.add(s);
        if(!set.contains(endGene)) return -1;//优化2
        Set<String> vis = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        char[] ck = {'A','C','G','T'};//优化3
        queue.add(startGene);
        int ret=0;
        while(!queue.isEmpty()) {
            int sz = queue.size();
            ret++;
            for(int i=sz;i>0;i--) {
                String t = queue.poll();
                if(t.equals(endGene)) return ret;
                vis.add(t);
                for(int j=0;j<8;j++) {
                    //每次改变一个字符，并查看是否在基因库中和不在vis中(不在证明没有被搜索过)
                    StringBuilder tmp = new StringBuilder(t);
                    for(int k=0;k<4;k++) {//优化3
                        String str = tmp.replace(j,j+1,ck[k]+"").toString();
                        if(str.equals(endGene)) return ret;
                        if(set.contains(str) && !vis.contains(str)) {
                            queue.add(str);
                            vis.add(str);
                        }
                    }
                }
            }
        }
        return -1;
    }


    //最长回文串
    public int longestPalindromes(String s) {
        int[] map1 = new int[26];//小写
        int[] map2 = new int[26];//大写
        for(int i=0;i<s.length();i++) {
            char ch = s.charAt(i);
            if(Character.isUpperCase(ch)) map2[(int)ch-65]++;
            else map1[(int)ch-97]++;
        }
        boolean bool1 = false;
        boolean bool2 = false;
        int ret=0;
        for(int i=0;i<26;i++) {
            if(map1[i]!=0 && map1[i]%2==0) {
                ret+=map1[i];
            }else if(map1[i]>=1){
                ret+=map1[i]-1;
                bool1=true;
            }
            if(map2[i]!=0 && map2[i]%2==0) {
                ret+=map2[i];
            }else if(map2[i]>=1){
                ret+=map2[i]-1;
                bool2=true;
            }
        }
        if(bool1 || bool2 ) ret++;
        return ret;
    }
    //5.最长回文子串
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        char[] str = s.toCharArray();
        String ret = new String();
        for(int i=n-1;i>=0;i--) {
            for(int j=i;j<n;j++) {
                if(str[i]==str[j]) {
                    if(i == j) dp[i][j]=true;
                    else if(i+1 == j) dp[i][j]=true;
                    else dp[i][j]=dp[i+1][j-1];
                }
                if(dp[i][j]) {
                    if(ret.length()<j-i+1) {
                        ret = s.substring(i,j+1);
                    }
                }
            }
        }
        return ret;
    }
    //回文子串
    public int countSubstrings(String s) {
        int n = s.length();
        if(n==1) return 1;
        boolean[][] dp = new boolean[n][n];
        char[] str = s.toCharArray();
        int ret=0;
        for(int i=n-1;i>=0;i--) {
            for(int j=i;j<n;j++) {
                if(str[i]==str[j]) {
                    if(i == j) dp[i][j]=true;
                    else if(i+1 == j) dp[i][j]=true;
                    else dp[i][j]=dp[i+1][j-1];
                }
                if(dp[i][j]) ret++;
            }
        }
        return ret;
    }

}
